package sort

// MergeSort [l, r]
func MergeSort(data []int, l, r int) {
	if l >= r {
		return
	}

	mid := l + (r-l)/2
	MergeSort(data, l, mid)
	MergeSort(data, mid+1, r)
	merge(data, l, mid, r)
}

func merge(data []int, l, mid, r int) {
	var dup = make([]int, r-l+1)
	copy(dup, data[l:r+1]) // 拷贝一份 [l,r] 内容， 准备merge

	i, j := l, mid+1
	for k := l; k <= r; k++ {
		switch {
		case i > mid:
			data[k] = dup[j-l]
			j++
		case j > r:
			data[k] = dup[i-l]
			i++
		case dup[i-l] < dup[j-l]:
			data[k] = dup[i-l]
			i++
		default:
			data[k] = dup[j-l]
			j++
		}
	}
}
